Lemme
L'algorithme d'Euclide est basé sur le lemme suivant :
Soit \(a,b\in\Bbb N^\star\)
Si on écrit la division euclidienne de \(a\) par \(b\), \(a=bq+r\) avec \(0\leqslant r\lt b\), alors $$\operatorname{pgcd}(a,b)={{\operatorname{pgcd}(b,r)}}$$
(
Division euclidienne,
Pgcd)
Démonstration : ^[
![](.\Img\Pasted image 20220321093722.png)
(
Division - Diviseur - Divisibilité)]
Algorithme
Algorithme d'Euclide :
Soit \(a\geqslant b\). On cherche \(\operatorname{pgcd}(a,b)\)- On effectue \(a=bq_1+r_1\) avec \(0\leqslant r_1\lt b\)
>- si \(r_1=0\), alors \(\operatorname{pgcd}(a,b)=\operatorname{pgcd}(b,0)=b\)
>- si \(r_1\gt 0\), on effectue \(b=r_1q_2+r_2\) et on applique le lemme
Exemples